package com.zp.self.module.level_4_算法练习.数据结构.二叉树;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author By ZengPeng
 */
public class 力扣_872_叶子相似的树 {
    @Test
    public void main() {

        Solution solution = new 力扣_872_叶子相似的树().new Solution();
        System.out.println(solution);
    }

    /**
     题目：请考虑一棵二叉树上所有的叶子，这些叶子的值按从左到右的顺序排列形成一个 叶值序列 。
         举个例子，如上图所示，给定一棵叶值序列为 (6, 7, 4, 9, 8) 的树。
         如果有两棵二叉树的叶值序列是相同，那么我们就认为它们是 叶相似 的。
         如果给定的两个根结点分别为 root1 和 root2 的树是叶相似的，则返回 true；否则返回 false 。

     示例 1：
     输入：root1 = [3,5,1,6,2,9,8,null,null,7,4], root2 = [3,5,1,6,7,4,2,null,null,null,null,null,null,9,8]
     输出：true

     示例 2：
     输入：root1 = [1,2,3], root2 = [1,3,2]
     输出：false

     分析：【P 💖】
        1.深度优先遍历：将子叶节点存储到List,再对比
                    --执行耗时:0 ms,击败了100.00% 的Java用户
                    --编码耗时: 10:40

     边界值 & 注意点：
        1.
     **/
//leetcode submit region begin(Prohibit modification and deletion)

    class Solution {
        public boolean leafSimilar(TreeNode root1, TreeNode root2) {
            List<Integer> list1 = new ArrayList<>();
            List<Integer> list2 = new ArrayList<>();
            dfs(root1, list1);
            dfs(root2, list2);
            if(list1.size()!=list2.size())return
                false;
            for (int i = 0; i < list1.size(); i++) {
                if(!list1.get(i).equals(list2.get(i)))
                    return false;
            }
            return true;
        }

        private void dfs(TreeNode root1, List<Integer> list0) {
            if(root1==null)return;
            if(root1.left==null && root1.right==null){
                list0.add(root1.val);
            }else {
                dfs(root1.left,list0);
                dfs(root1.right,list0);
            }
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}

